package com.chj.nk.gaojishizhan2020xia.class09.copy;

//https://www.cnblogs.com/grandyang/p/4575026.html
//https://blog.csdn.net/qq_34342154/article/details/78427813
//https://www.cnblogs.com/grandyang/p/4575026.html
public class Code02_CandyProblem {
	public static int candy1(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int pre = nextMinIndex1(arr, 0);
		int res = rightCands(arr, 0, pre++);
		int lbase = 1;
		int next = 0;
		int rcands = 0;
		int rbase = 0;
		while (pre != arr.length) {
			if (arr[pre] > arr[pre - 1]) {
				res += ++lbase;
				pre++;
			} else if (arr[pre] < arr[pre - 1]) {
				next = nextMinIndex1(arr, pre - 1);
				rcands = rightCands(arr, pre - 1, next++);
				rbase = next - pre + 1;
				res += rcands + (rbase > lbase ? -lbase : -rbase);
				lbase = 1;
				pre = next;
			} else {
				res += 1;
				lbase = 1;
				pre++;
			}
		}
		return res;
	}

	public static int nextMinIndex1(int[] arr, int start) {
		for (int i = start; i != arr.length - 1; i++) {
			if (arr[i] <= arr[i + 1]) {
				return i;
			}
		}
		return arr.length - 1;
	}

	public static int rightCands(int[] arr, int left, int right) {
		int n = right - left + 1;
		return n + n * (n - 1) / 2;
	}

	public static int candy2(int[] arr) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int index = nextMinIndex2(arr, 0);
		int[] data = rightCandsAndBase(arr, 0, index++);
		// cands, base
		int res = data[0];
		int lbase = 1;
		int same = 1;
		int next = 0;
		while (index != arr.length) {
			if (arr[index] > arr[index - 1]) {
				res += ++lbase;
				same = 1;
				index++;
			} else if (arr[index] < arr[index - 1]) {
				next = nextMinIndex2(arr, index - 1);
				data = rightCandsAndBase(arr, index - 1, next++);
				if (data[1] <= lbase) {
					res += data[0] - data[1];
				} else {
					res += -lbase * same + data[0] - data[1] + data[1] * same;
				}
				index = next;
				lbase = 1;
				same = 1;
			} else {
				res += lbase;
				same++;
				index++;
			}
		}
		return res;
	}

	public static int nextMinIndex2(int[] arr, int start) {
		for (int i = start; i != arr.length - 1; i++) {
			if (arr[i] < arr[i + 1]) {
				return i;
			}
		}
		return arr.length - 1;
	}

	public static int[] rightCandsAndBase(int[] arr, int left, int right) {
		int base = 1;
		int cands = 1;
		for (int i = right - 1; i >= left; i--) {
			if (arr[i] == arr[i + 1]) {
				cands += base;
			} else {
				cands += ++base;
			}
		}
		return new int[] { cands, base };
	}

	public static int candy3(int[] ratings) {
		if (ratings.length == 0)
			return 0;
		int res = 1, pre = 1, cnt = 0;
		for (int i = 1; i < ratings.length; ++i) {
			if (ratings[i] >= ratings[i - 1]) {
				if (cnt > 0) {
					res += cnt * (cnt + 1) / 2;
					if (cnt >= pre)
						res += cnt - pre + 1;
					cnt = 0;
					pre = 1;
				}
				pre = (ratings[i] == ratings[i - 1]) ? 1 : pre + 1;
				res += pre;
			} else {
				++cnt;
			}
		}
		if (cnt > 0) {
			res += cnt * (cnt + 1) / 2;
			if (cnt >= pre)
				res += cnt - pre + 1;
		}
		return res;
	}

	public static int candy4(int[] ratings) {
		int n = ratings.length;
		int total = 0;
		int down = 0;
		int pre = 1;
		// 1.
		for (int i = 1; i < n; i++) {
			// 1.1当前是在上坡或者平坡
			if (ratings[i] >= ratings[i - 1]) {

				// 1.1.1之前出现过了下坡
				if (down > 0) {
					// 山顶的糖果数大于下降的高度，对应情况 1
					// 将下降的糖果数利用等差公式计算，单独加上山顶
					if (pre > down) {
						total += count(down);
						total += pre;
						// 山顶的糖果数小于下降的高度，对应情况 3，
						// 将山顶也按照等差公式直接计算进去累加
					} else {
						total += count(down + 1);
					}

					// 当前是上坡，对应情况 1 或者 3
					// 更新 pre 等于 2
					if (ratings[i] > ratings[i - 1]) {
						pre = 2;

						// 当前是平坡，对应情况 2 或者 4
						// 更新 pre 等于 1
					} else {
						pre = 1;
					}
					down = 0;

					// 1.1.2之前没有出现过下坡
				} else {
					// 将前一个小朋友的糖果数相加
					total += pre;
					// 如果是上坡更新当前糖果数是上一个的加 1
					if (ratings[i] > ratings[i - 1]) {
						pre = pre + 1;
						// 如果是平坡，更新当前糖果数为 1
					} else {
						pre = 1;
					}

				}

			} else if (ratings[i] < ratings[i - 1]) {
				// 1.2
				// 如果当前的 rating 比前一个的 rating 小，
				// 说明开始走下坡，
				// 用down变量记录连续多少次下降，
				// 此时的 pre记录的就是从左边山底到山底的高度。
				// 当出现平坡或上坡的时候，
				// 将所有的下坡的糖果数利用等差公式计算。
				// 此外根据 pre 和 down 决定山顶的糖果数。
				down++;
			}
		}

		// 2.判断是否有下坡
		if (down > 0) {
			// 和之前的逻辑一样进行相加
			// 山顶的糖果数大于下降的高度，对应情况 1
			// 将下降的糖果数利用等差公式计算，单独加上山顶
			if (pre > down) {
				total += count(down);
				total += pre;

				// 山顶的糖果数小于下降的高度，对应情况 3，
				// 将山顶也按照等差公式直接计算进去累加
			} else {
				total += count(down + 1);
			}

			// 3.将最后一个小朋友的糖果计算
			// 当前是上坡，对应情况 1 或者 3
		} else {
			total += pre;
		}

		return total;
	}

	// 等差数列求和
	private static int count(int n) {
		return (1 + n) * n / 2;
	}

	//
	// 作者：windliang
	// 链接：https://leetcode-cn.com/problems/candy/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-31/
	// 来源：力扣（LeetCode）
	// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

	public static void main(String[] args) {
		// int[] test1 = { 3, 0, 5, 5, 4, 4, 0 };
		// // int[] test3 = { 1, 5, 4, 3, 2, 1 };
		// int[] test3 = { 1, 2, 3, 4, 5, 1 };
		// System.out.println(candy1(test1));
		// System.out.println(candy1(test3));
		//
		// // int[] test2 = { 3, 0, 5, 5, 4, 4, 0 };
		// // System.out.println(candy2(test2));
		//
		// // int[] test3 = { 1, 5, 4, 3, 2, 1 };
		// System.out.println(candy1(test1));
		// System.out.println(candy3(test3));

		int[] test2 = { 1, 5, 5, 5, 4, 3, 2, 1 };
		System.out.println(candy2(test2));
	}

}
